/*
 * Copyright (C) 2004-2005, Universidade Federal de Campina Grande. All rights reserved.
 */
package org.epanetgrid.otimizacao.searchspace;

import java.math.BigInteger;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import org.jheuristics.DefaultIndividual;
import org.jheuristics.util.BitString;

/**
 *	Retorna uma lista de todos os indiv�duos poss�veis, que cobrem todo o espa�o de busca.
 *
 * @author Marcell Manfrin, 04/05/2005
 */
public class CompleteSearchSpaceUtils {

	/**
	 *
	 * @param numeroDeIntervalos N�mero de intervalos da simula��o
	 * @param numeroDeBombas Quantidade de bombas presentes na malha
	 * @return Lista com todos os indiv�duos que cobrem todo o espa�o de busca
	 */
	public static List completeListOfIndividuals(int numeroDeIntervalos, int numeroDeBombas) {
		List gens = new LinkedList();
		List bitStringPossiveis = completeListOfBitStrings(numeroDeBombas);
		if (numeroDeIntervalos == 0) {
			gens = bitStringPossiveis;
		} else {
			List inicial = new LinkedList();
			for (Iterator it = bitStringPossiveis.iterator(); it.hasNext(); ) {
				List tmp = new LinkedList();
				tmp.add(it.next());
				inicial.add(tmp);
			}
			for (int i = 1; i < numeroDeIntervalos; i++) {
				inicial = combinate(inicial, bitStringPossiveis);
			}
			gens.addAll(inicial);
		}
		List result = new LinkedList();
		for (Iterator it = gens.iterator(); it.hasNext(); ) {
			result.add(new DefaultIndividual(it.next()));
		}
		return result;
	}

	/**
	 * 
	 * @param numeroDeBits
	 * @return
	 */
	protected static List<BitString> completeListOfBitStrings(int numeroDeBits) {
		if (0 > numeroDeBits) {
			throw new IllegalArgumentException();
		}
		List<BitString> result = new LinkedList<BitString>();
		BigInteger two = new BigInteger("2");
		BigInteger numeroDeBitStrings = two.pow(numeroDeBits);
		for (BigInteger integer = BigInteger.ZERO; integer.compareTo(numeroDeBitStrings) < 0; integer = integer.add(BigInteger.ONE)) {
			result.add(new BitString(numeroDeBits));
		}
		for (int i = 0; i < numeroDeBits; i++) {
			Iterator it = result.iterator();
			boolean valor = false;

			while (it.hasNext()) {
				for (BigInteger integer = BigInteger.ZERO, max = numeroDeBitStrings.divide(two.pow(i+1)); integer.compareTo(max) < 0; integer = integer.add(BigInteger.ONE)) {
					((BitString)it.next()).set(i, valor);
				}
				valor = !valor;
			}
		}
		return result;
	}

	/**
	 * 
	 * @param one
	 * @param bitStrings
	 * @return
	 */
	private static List combinate(List one, List bitStrings) {
		List result = new LinkedList();
		for (Iterator it1 = one.iterator(); it1.hasNext(); ) {
			List element = (List) it1.next();
			for (Iterator it2 = bitStrings.iterator(); it2.hasNext(); ) {
				List tmp = new LinkedList();
				tmp.addAll(element);
				tmp.add(it2.next());
				result.add(tmp);
			}
		}
		return result;
	}

}
